import java.util.Stack;

/**
 * @program: leetcode739
 * @author: JCM
 * @create: 2023-02-21 12:49
 * @description:
 **/

class Solution {
    /**
     * 穷举法
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures1(int[] temperatures) {
        int[] ans = new int[temperatures.length];
        for(int i = 0; i < temperatures.length-1; i++) {
            for(int j = i+1; j < temperatures.length; j++) {
                if(i > 0) {
                    if(temperatures[i-1] == temperatures[i]) {
                        if(ans[i-1] != 0) {
                            ans[i] = ans[i-1]-1;
                        }else {
                            ans[i] = 0;
                        }
                        break;
                    }
                }

                if(temperatures[i] < temperatures[j]) {
                    ans[i] = j-i;
                    break;
                }
            }
        }
        ans[temperatures.length-1] = 0;
        return ans;
    }

    /**
     * 单调栈解法
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < len; i++) {
            // 如果温度小于栈顶温度，直接入栈
            if(temperatures[i] <= temperatures[stack.peek()]) {
                stack.push(i);
            }else {
                // 当温度大于栈顶温度时，先在 ans 中记录下天数，然后进行出栈
                // 出栈之后，再将新的栈顶元素重复此操作
                while(!stack.isEmpty() &&
                        temperatures[i] > temperatures[stack.peek()]) {
                    ans[stack.peek()] = i-stack.peek();
                    stack.pop();
                }
                // 不要忘记比较完之后将当前温度 入栈！！！
                stack.push(i);
            }
        }
        return ans;
    }
}
public class Main {

}
